package week_nine;

public class ImplementStrStr_28 {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        int[] next = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                System.out.print("i: " + i + " j: " + j);
                j = next[j - 1];//跳转到最大公共子串的下一个位置开始比较（next值代表前缀长度==下一个可以比较的字符的下标）
                System.out.println(" next j: " + j);
            }
            if (needle.charAt(i) == needle.charAt(j)) j++;
            next[i] = j;//更新next位置
            System.out.println(i + " next j: " + j);
        }

        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];//右推
                System.out.println(" next j: " + j);
            }
            if (haystack.charAt(i) == needle.charAt(j)) j++;
            System.out.println("s " + i + " next j: " + j);

            if (j == m) return i - m + 1;//结束
        }
        return -1;
    }

    public static void main(String[] args) {
        int i = new ImplementStrStr_28().strStr("abbstabbecabbstabb3abbstabbecabbstabbx", "abbstabbecabbstabbx");
        System.out.println(i);
    }
}
